package P493_翻转对;

import java.util.Arrays;

/**
 * 493. 翻转对
 * 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
 * <p>
 * 你需要返回给定数组中的重要翻转对的数量。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,3,2,3,1]
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: [2,4,3,5,1]
 * 输出: 3
 * 注意:
 * <p>
 * 给定数组的长度不会超过50000。
 * 输入数组中的所有数字都在32位整数的表示范围内。
 */
public class Solution {
    //很显然，不能暴力法，这个会超时，n^2
    //找规律，因为 i < j且nums[i] > 2*nums[j]的时候,如果 i<m<j，且有num[m] > 2*num[j]，是不是 m和j也是这么一个翻转对呢
    //如果他们是一个排好序的小数组，那么 i右边的，全部都是可以保证nums[m] > nums[i] > 2*nums[j] 了，那么这一大票就都能加入了

    //当然，如果是一个排序好的小数组，他们的顺序已经打乱，不能保证索引值i j k的原始位置大小
    //这里就要考虑二分/归并， 因为把原来的数组切分，我能保证左边部分的索引值，一定全部小于右边部分的索引值
    //nums[i..m...j]分为left = nums[i..m],和right = nums[m+1...j],所有left里面的原始索引值都比right对应的原始索引值小
    //那么，给left和right排序之后，left中的某个i和right中的某个j，如果保证一定有i < j，如果有nums[i] > 2*nums[j],那么对于left中i的右边部分，也全部满足

    //对于 left 和right这两个子数组   left的i从最左边开始  right的j从最右边开始，两个指针往中间靠拢

    //总之，结果就是 left内部的翻转对  + right内部的翻转对 + left和right两个区间之间的翻转对
    // (left下表i从最左开始，right下表j从最右开始，往中靠拢，一旦有条件满足nums[i] > 2*nums[j]，那么对于i为左边而言，满足的有right中所有在j左边的，对于j未右边而言，满足的有left种所有在i右边的)

    int countAll = 0;

    //其实就是一步步，做归并排序，在归并步骤的时候，顺带做一下左右两个区间的翻转对查找
    private int[] doPart(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return nums;
        }

        int[] left = new int[len / 2];
        int[] right = new int[len - len / 2];
        System.arraycopy(nums, 0, left, 0, len / 2);
        System.arraycopy(nums, len / 2, right, 0, len - len / 2);

        int[] newLeft = doPart(left);
        int[] newRight = doPart(right);
        int[] newArr = merge(newLeft, newRight);
        //归并排序，归并merge步骤的时候，做一下左右区间的翻转对查找
        int c = twoArraysCheck(newLeft, newRight);
        countAll += c;
        return newArr;

    }

    //归并常规merge
    private int[] merge(int[] left, int[] right) {
        int[] newArr = new int[left.length + right.length];
        int i = 0, j = 0, index = 0;
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                newArr[index++] = left[i++];
            } else {
                newArr[index++] = right[j++];
            }
        }
        while (i < left.length) {
            newArr[index++] = left[i++];
        }
        while (j < right.length) {
            newArr[index++] = right[j++];
        }
        return newArr;
    }

    //进来的左和右两个，找两个区间之间的翻转对数量
    private int twoArraysCheck(int[] left, int[] right) {

        int count = 0, i = 0, j = 0;
        while (i < left.length) {
            while (j < right.length && (long) left[i] > 2 * (long) right[j]) {
                j++;
            }
            count += j;
            i++;
        }
//        while(j < right.length){
//            i = 0;
//            while(i < left.length){
//                //!!!注意乘法的溢出问题
//                if((long)left[i] > 2 * (long)right[j]){
//                    count += left.length - i;
//                    break;
//                }
//                i++;
//            }
//            j++;
//        }
        return count;


    }

    //上面的几个在一起也能跑，这里跑在一个方法里面
    public int doItInOneMethod(int[] nums, int left, int right){
        if(left == right){
            return 0;
        }
        int mid = (left + right)/2;

        int leftRet = doItInOneMethod(nums, left, mid);
        int rightRet = doItInOneMethod(nums,mid+1, right);

        //=============================下面这段，就是归并排序中没有的，本算法中需要添加的这个

        //ret 除了这两个里面的，还要再加上这两个之间的映射
        int ret = leftRet + rightRet;

        //注意,left,mid,right都是原始索引值，所以下面都有等号,可以取到这个边界
        //TODO 这段竟然超时了
        // 首先统计下标对的数量

        int i = left, j = mid+1;
//        while(j <= right){
//            //TODO 致命问题在这： 每次i都从头开始遍历！
//            //TODO 这里是每次找[满足]的，下面的官方方法是，每次开始找j，找到[不满足]的，那么它前面的就都满足，且后面的都不满足
//            i = left;
//            while(i <= mid){
//                //!!!注意乘法的溢出问题
//                if((long)nums[i] > 2 * (long)nums[j]){
//                    ret += mid - i + 1;
//                    break;
//                }
//                i++;
//            }
//            j++;
//        }

        //===================以下为官方方法
        while (i <= mid) {
            while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
                j++;
            }
            //每次都是从右边数组的第一个截止到某个不能再走的位置j位置，之所以不用j每次从0开始，是因为，j左边的数小，i++后的数一定比刚才已经走过的j的左边大
            ret += j - mid - 1;
            i++;
        }
        //===============================
        //然后将当前的[left,mid][mid+1,right-1]两个有序数组合并成大的，借助辅助空间
        //注意,left,mid,right都是原始索引值，所以下面都有等号,可以取到这个边界
        int [] sorted = new int[right-left + 1];
        int p = left,q=mid+1,index=0;
        while(p <= mid && q <= right){
            if(nums[p] < nums[q]){
                sorted[index++] = nums[p++];
            }else{
                sorted[index++] = nums[q++];
            }
        }
        while (p <= mid) sorted[index++] = nums[p++];
        while (q <= right) sorted[index++] = nums[q++];
        //将sorted数组还原到Nums中
//        for(int k = 0;k< right - left  +1;k++){
//            nums[left + k] = sorted[k];
//        }
        //用系统方法也行
        System.arraycopy(sorted,0,nums,left,right-left+1);
        return ret;
    }
    public int reversePairs(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        System.out.println(Arrays.toString(doPart(nums)));
        System.out.println(countAll);

        int x = doItInOneMethod(nums, 0, nums.length - 1);
        return x;

    }

    public static void main(String args[]) {
        //System.out.println(new P493.Solution().twoArraysCheck(new int[]{1, 3, 13, 20}, new int[]{1, 5, 12, 32}));
//        System.out.println(new P493.Solution().reversePairs(new int[]{2147483647,2147483647,2147483647,2147483647,2147483647,2147483647}));
        System.out.println(new P493_翻转对.Solution().reversePairs(new int[]{1,3,2,3,1,32,12,5,6,7,4,2,666,12,3,44,1,3,3,32,100,3,3,4,4,5,6,23,5,1,1,2,3,44,455}));
    }
}
